<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8" />
    <meta
      name="viewport"
      content="width=device-width, initial-scale=1.0, user-scalable=no"
    />
    <title>标题</title>
  </head>

  <body>
    <script>
      /* 
            时间O(nlogn)
            空间O(n)
            出错：1. 重复的元素 >=
                2. 删除元素代码注意熟悉怒
        */
      function sortArray(arr) {
        let start = 0;
        let end = arr.length - 1;
        quickSort(arr, start, end);
        return arr;
      }

      function quickSort(arr, start, end) {
        if (start > end) {
          return;
        }
        let privt = getPrivt(arr, start, end);
        quickSort(arr, start, privt - 1);
        quickSort(arr, privt + 1, end);
      }

      function getPrivt(arr, start, end) {
        let left = start;
        let right = end;
        let priVal = arr[start];

        while (left < right) {
          while (left < right && arr[right] > priVal) {
            right--;
          }

          while (left < right && arr[left] <= priVal) {
            left++;
          }

          if (left < right) {
            let temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
          }
        }

        arr[start] = arr[left];
        arr[left] = priVal;

        return left;
      }
      let test3 = [5, 1, 1, 2, 0, 0];
      // console.log(sortArray(test1));
      // console.log(sortArray(test2));
      console.log(quickSort(test3));
    </script>
  </body>
</html>
